//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define ll long long
#define int long long
//#define ull unsigned long long
//#define lll __int128
#define fi first
#define se second
//#define double long double
using namespace std;
const long long INF=1e16+5;
const long long mod=998244353,orm=3;
//const long long mod=1000000007;
const int MAXN=1000005;
const double eps=1e-6;
bool ST;
vector<int> v[MAXN];
int ty,T,n,m;
int dis[MAXN];
int mp[2005][2005];
struct o {
	int x,y;
}e[MAXN];
void solve() {
	cin>>n>>m;
	for(int i=1;i<=m;i++) {
		int x,y;cin>>x>>y;
		v[x].push_back(y),v[y].push_back(x);
		e[i]={x,y};
	}
	int ans=-INF;
	for(int i=1;i<=m;i++) {
		queue<int> q;
		int x=e[i].x,y=e[i].y;
		for(int j=1;j<=n;j++) dis[j]=n+1;dis[x]=0,q.push(x);
		while(!q.empty()) {
			int u=q.front();q.pop();
			for(int to:v[u]) {
				if(u==x&&to==y) continue;
				if(u==y&&to==x) continue;
				if(dis[to]>dis[u]+1) {
					dis[to]=dis[u]+1;q.push(to);
				}
			}
		}
		ans=max(ans,-(m-1+dis[y]));
	}
	cout<<ans<<" "<<0<<"\n";
	for(int i=0;i<=n;i++) v[i].clear();
}
bool ED;
signed main() {
//	cout<<(&ST-&ED)/1024.0/1024.0;
	freopen("oi.in","r",stdin);
	freopen("oi.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>ty>>T;while(T--) solve();
	return 0;
}
